#==============================================================================
#
#  $Id$
#
"""
    Generalized b-tree implementation.  This includes two concrete classes, 
    BTree and BList, that can be used as stand-alone data structures or can 
    have storage mechanisms plugged in to provide persistence.
"""
#
#   Copyright (C) 2007 Michael A. Muller
#
#   This file is part of ODB.
#
#   ODB is free software: you can redistribute it and/or modify it under the 
#   terms of the GNU Lesser General Public License as published by the Free 
#   Software Foundation, either version 3 of the License, or (at your option) 
#   any later version.
#
#   ODB is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU Lesser General Public License for more details.
#
#   You should have received a copy of the GNU Lesser General Public License 
#   along with ODB.  If not, see <http://www.gnu.org/licenses/>.
#
#==============================================================================

import sys, copy, pickle
from cStringIO import StringIO
from odbi import DB

class NodeData:
    """
        Stores information about a single node in the tree for use by FindData.
    """
    
    def __init__(self, node, parent):
        
        # the current BTreeNode
        self.node = node
        
        # the parent NodeData
        self.parent = parent
        
        # the slot index of the slot under /node/.  Note that this may be -1 
        # in the case when referencing the bottom of a node with no slots 
        # (which only happens when we have an empty root node)
        self.slotIndex = 0

class FindData(object):
    """
        Stores information to be used by a BTree during a find operation.
    """
    
    def __init__(self, node = None):
        self._node = node
        
        # true or false depending on whether an element was found - if False, 
        # node is None
        self.found = False
        
        # this is a flag used to communicate that the find is already out 
        # of bounds - that is, the thing we're looking for is known to be 
        # greater than the greatest item in the tree.  This information gets 
        # passed down through the find both as an optimization and a final 
        # determination that the node was not found.
        self.outside = False
    
    
    def __getNode(self): return self._node.node
    node = property(__getNode, None, None,
                    "The current node (BTreeNode instance)"
                    )

    def __getSlotIndex(self): return self._node.slotIndex
    def __setSlotIndex(self, val): self._node.slotIndex = val
    slotIndex = property(__getSlotIndex, __setSlotIndex, None,
                         "index of the current child slot - note that this is "
                          "the index of the _child_ of self.node, not the "
                          "index of the node itself."
                         )
    
    def nextSlot(self):
        self.slotIndex += 1
    
    def prevSlot(self):
        self.slotIndex -= 1
    
    def lastSlot(self):
        """
            Point to the end of the slots.  This involves pointing the slot 
            index at the last slot and also setting "outside"
        """
        self.slotIndex = len(self.node._slots) - 1
        self.outside = True

    def _createNodeData(self, node, parent):
        return NodeData(node, parent)

    def push(self, node):
        self._node = self._createNodeData(node, self._node)
    
    def clonePush(self, node):
        clone = self._clone()
        clone.push(node)
        return clone

    def _clone(self):
        return copy.copy(self)

    def getParent(self):
        if not self._node or not self._node.parent:
            return None
        parentData = self._clone()
        parentData._node = self._node.parent
        return parentData

class KeyMaster:
    """
        Base class for classes that determine whether a key belongs in a 
        particular slot.
    """
    
    def create(self, initializer = None):
        """
            Returns a KeyMaster instance for a new node.
            
            parms:
                initializer: [any or None] if present, this is an initializer 
                    that is appropriate for the key type.
        """
        raise NotImplementedError()
    
    def init(self, node):
        """
            Called to initialize a new node.
            
            Parms:
                node: [@BTreeNode]
        """
        raise NotImplementedError()
    
    def handleSlotsChanged(self, node, findData):
        """
            Called whenever the slots in the node change apart from a simple 
            removal.  This will be called on nodes that are split or merged.
            Unlike handleRemoval() and handleInsertion it will not be called 
            on their ancestors.
            
            Parms:
                node: [@BTreeMeat]
                findData: [@FindData]
        """
        raise NotImplementedError()
    
    def handleRemoval(self, node):
        """
            Called when a descendant is removed.  This will be called for 
            nodes that have children removed and for all of their ancestors.
        """
        raise NotImplementedError()
    
    def handleInsertion(self, node):
        """
            Called when a descendant is inserted.  This will be called for 
            nodes that have children inserted and for all of their ancestors.
        """
        raise NotImplementedError()
    
    def likesKey(self, node, findData):
        """
            Returns true if the key identified by findData belongs in the 
            specified node.
            Parms:
                node: [@BTreeNode]
                findData: [@FindData]
        """
        raise NotImplementedError()
    
    def matchesKey(self, node, findData):
        """
            Returns true if the key identified by findData exactly matches 
            that of the specified node.
            
            parms:
                node: [@BTreeNode]
                findData: [@FindData]
        """
        raise NotImplementedError()
    
    def getKey(self, findData):
        """
            Returns the key (whatever that may be in the implementation).
            
            parms:
                findData: [@FindData]
        """
        raise NotImplementedError()
    
    def setKey(self, findData):
        """
            Sets the key from the key defined in the findData.
            
            parms:
                findData: [@FindData]
        """
        raise NotImplementedError()

class FakeKeyMaster(KeyMaster):
    """
        Used for the construction of fake nodes for keys that are not found.
    """
    
    def init(self, elem):
        pass
    
    def getKey(self, findData):
        return None

class Storage:
    """
        Base class for classes that manage node storage.
    """
    
    def markModified(self,  node):
        """
            Marks the node as modified.
        """
        raise NotImplementedError()
    
    def markKeyModified(self, node):
        """
            Marks the nodes key as modified.
        """
        raise NotImplementedError()
    
    def markDeleted(self, node):
        """
            Marks the node as deleted.
        """
        raise NotImplementedError()
    
    def insureReadable(self, node):
        """
            Insure that the node is fully loaded from its storage and is ready 
            to read.
        """
        raise NotImplementedError()
    
    def create(self):
        """
            Returns a storage instance for a new node.
            
            Although the name is create, it is not necessary to create a new 
            node.  If the storage system requires no node-specific state, we 
            could simply return the existing node.
        """
        raise NotImplementedError()
    
    def isCheckpointable(self):
        """
            Returns true if the node should be considered during checkpointing.
        """
        raise NotImplementedError()

def serialize(obj):
    """
        Returns a string representing the serialized form of the object.
    """
    return pickle.dumps(obj)

def deserialize(data):
    """
        Returns an object deserialized from the data.
    """
    return pickle.loads(data)

class BTreeNode(object):
    """
        Base class for all different types of BTree nodes.
    """
    
    # max and minimum children for each node
    MAX_SLOTS = 3
    MIN_SLOTS = 2
    
    def __init__(self, keyMaster, storage):
        self._keyMaster = keyMaster
        self._storage = storage
    
    def find(self, findData):
        """
            Sets the given findData to the appropriate node in the tree.
            
            Must be implemented by derived classes.
        """
        raise NotImplementedError()
        
    def redistribute(self, findData, index):
        raise NotImplementedError()
    
    def dump(self, prefix = '', out = sys.stdout):
        raise NotImplementedError()
    
    def findFirst(self, findData):
        """
            Position find data at the position before the first element in the 
            tree.
        """
        raise NotImplementedError()
    
    def findLast(self, findData):
        """
            Positions findData at the position after the last element in the 
            tree.
        """
        raise NotImplementedError()
    
    def remove(self, findData):
        """
            Remove the node identified by the find data and reorganize the 
            tree accordingly.
        """
        raise NotImplementedError()

    def next(self, findData):
        """
            Returns a FindData instance for the next position in the tree.
        """
        raise NotImplementedError()
    
    def prev(self, findData):
        """
            Returns a FindData instance for the previous position in the tree.
        """
        raise NotImplementedError()
    
    def checkpoint(self):
        """
            Checkpoints the node and all of its descendents.
            
            Returns true if the parent needs to be marked modified as a result 
            of the checkpointing action.
        """
        raise NotImplementedError()
    
    def getNodeIter(self):
        """
            Returns an iterator over all of the nodes in the tree.
        """
        raise NotImplementedError()

class BTreeElem(BTreeNode):
    """
        A b-tree element.
    """
    
    def __init__(self, val, keyMaster, storage):
        BTreeNode.__init__(self, keyMaster, storage)
        self.__setVal(val)
        keyMaster.init(self)

    def __setVal(self, val):
        self.rawVal = serialize(val)
    
    def __getVal(self):
        return deserialize(self.rawVal)
    
    val = property(__getVal, __setVal, None,
                   'The value object of the btree node.  The object will '
                    'be serialized when stored, and deserialized when '
                    "accessed, so don't expect to get back the same object "
                    'twice!'
                   )

    def find(self, findData):
        # the buck ends here...
        findData.push(self)
        findData.found = self._keyMaster.matchesKey(self, findData)
        if self._storage:
            self._storage.insureReadable(self)

    def remove(self, findData):
        parentFindData = findData.getParent()
        if self._storage: self._storage.markDeleted(self)
        parentFindData.node.remove(parentFindData)

    def dump(self, prefix = '', out = sys.stdout):
        if self._storage:
            self._storage.insureReadable(self)
            storageDump = ' {%s}' % self._storage
        else:
            storageDump = ''
        out.write('%s%s%s\n' % (prefix, self, storageDump))
    
    def __str__(self):
        return '%s%s' % (self._keyMaster.dumpToStr(), `self.val`)
    
    def findFirst(self, findData):
        findData.push(self)
        findData.found = True
        if self._storage: self._storage.insureReadable(self)
    
    def findLast(self, findData):
        findData.push(self)
        findData.found = False
    
    def next(self, findData):
    
        # back up to the parent, increment
        parent = findData.getParent()
        findData = parent.node.next(parent)
        
        # push down into the next child
        findData.push(findData.node._slots[findData.slotIndex])
        if findData.node._storage:
            findData.node._storage.insureReadable(findData.node)
        
        return findData

    def prev(self, findData):
        
        # if we're outside, this is easy.
        if findData.outside:
            
            # edge case: if we ended up creating a fake node, put us into a 
            # state where we are recognizably out of bounds
            if isinstance(self._keyMaster, FakeKeyMaster):
                findData.slotIndex = -1
            
            findData.outside = False
            if findData.node._storage: 
                findData.node._storage.insureReadable(findData.node)
            return findData

        # back up to the parent, decrement
        parent = findData.getParent()
        findData = parent.node.prev(parent)
        
        # push down into the previous child
        findData.push(findData.node._slots[findData.slotIndex])
        if findData.node._storage:
            findData.node._storage.insureReadable(findData.node)

        return findData
    
    def checkpoint(self):
        # we can only get here through a BTreeMeat node, and if he's got 
        # storage we should have storage too.
        return self._storage.checkpoint(self)
    
    def getNodeIter(self):
        if self._storage: self._storage.insureReadable(self)
        yield self

class BTreeMeat(BTreeNode):
    """
        BTree "meat" node.  The meat nodes all have a list of slots and know 
        about traversal.
    """
    def __init__(self, slots, keyMaster, storage):
        BTreeNode.__init__(self, keyMaster, storage)
        self._slots = slots
        keyMaster.init(self)

    def find(self, findData):
        """
            Finds the value specified by the findData (@FindData instance).
        """
        if self._storage: self._storage.insureReadable(self)

        findData.push(self)
        
        def notFound():
            # push a bogus node so iteration will still work
            findData.push(BTreeElem(None, FakeKeyMaster(), None))
            findData.found = False

        # this triggers an optimization - if we already know that the request 
        # is out of bounds, don't even bother searching through the slots, 
        # just go directly to the last element.
        if findData.outside:
            findData.lastSlot()
            if self._slots:
                self._slots[-1].find(findData)
            else:
                notFound()
            return
        
        slot = None
        for slot in self._slots:
            if slot._keyMaster.likesKey(slot, findData):
                slot.find(findData)
                break
            findData.nextSlot()
        else:
            # none of the slots was appropriate - use the last and back out 
            # the index ("outside" will indicate that we are beyond the end)
            findData.outside = True
            findData.prevSlot()
            if slot:
                slot.find(findData)
            else:
                notFound()

    def insert(self, findData, node):
        """
            Parms:
                findData: [@findData] data identifying a position in which to 
                    insert the node
                node: [@BTreeNode] the node to insert
        """
        slotIndex = findData.slotIndex + (findData.outside and 1 or 0)
        self._slots.insert(slotIndex, node)
        if self._storage: self._storage.markModified(self)
        self._keyMaster.handleInsertion(self)
        self._propagateChildInserted(findData, self.__checkMaximum())
    
    def childInserted(self, findData, splitChild):
        """
            Called when a new descendent has been inserted.
            
            parms:
                findData: [@findData]
                splitChild: [@BTreeNode or None] if this is provided, it is a 
                    new child to be inserted prior to the current child as the
                    result of a split.
        """
        self._keyMaster.handleInsertion(self)
        
        if splitChild:
            self._slots.insert(findData.slotIndex, splitChild)
            splitChild = self.__checkMaximum()
        
        self._propagateChildInserted(findData, splitChild)

    def _propagateChildInserted(self, findData, splitChild):
        pfd = findData.getParent()
        pfd.node.childInserted(pfd, splitChild)
    
    def __checkMaximum(self):
        if len(self._slots) > self.MAX_SLOTS:
            
            # split off a new node before the current node
            newNode = BTreeMeat(self._slots[:self.MIN_SLOTS], 
                                self._keyMaster.create(),
                                self._storage and self._storage.create()
                                )
            self._slots = self._slots[self.MIN_SLOTS:]
            self._keyMaster.handleSlotsChanged(self)
            
            return newNode
        else:
            return None
            
    def remove(self, findData):
        """
            Removes the child identified by findData.
            
            Parms:
                findData: [@FindData]
        """
        del self._slots[findData.slotIndex]
        if self._storage: self._storage.markModified(self)
        self.childRemoved(findData, False)
    
    def childRemoved(self, findData, rebalance):
        """
            Called to notify the parent of the removal of a descendent.
            
            parms:
                findData: [@FindData]
                rebalance: [boolean] if true, we need to perform a rebalance 
                    on this node because the child had fewer than the minimum 
                    number of children.
        """
        self._keyMaster.handleRemoval(self)
        
        # if the child requested a rebalance, do so.  We have to verify that 
        # there are enough slots to rebalance to deal with the root node.
        if rebalance and len(self._slots) > 1:
            self.rebalance(findData)
        
        # recurse to the parent
        self._propagateChildRemoved(findData)
    
    def _propagateChildRemoved(self, findData):
        pfd = findData.getParent()
        pfd.node.childRemoved(pfd, len(self._slots) < self.MIN_SLOTS)

#    def _checkMinimum(self, findData):
#        """
#            Returns true if the node was deleted in the process of rebalancing.
#        """
#        if len(self._slots) < self.MIN_SLOTS:
#            parentFinder = findData.getParent()
#            parentFinder.node.rebalance(parentFinder)
#            
#            # XXX hokiness ever begets hokiness.
#            return self not in parentFinder.node._slots
#        else:
#            return False
    
    def rebalance(self, findData):
        """
            Rebalance the node identified by findData after a delete.

            Parms:
                findData: [@FindData]
        """

        i = findData.slotIndex
        slot = self._slots[i]
        prevSlot = i > 0 and self._slots[i - 1]
        
        # if this is not the first slot, try to redistribute
        # with the slot before it
        if prevSlot and \
           prevSlot.redistribute(slot, findData.clonePush(prevSlot)):
            pass

        # if this is not the last slot, try to redistribute
        # with the one after it
        elif i < len(self._slots) - 1 and \
            slot.redistribute(self._slots[i + 1], findData.clonePush(slot)):
            pass

        # if that fails, merge with either of them - we rely 
        # on @merge() to mark the sibling as deleted
        elif i > 0:
            prevSlot.merge(slot, findData.clonePush(prevSlot))
            del self._slots[i]
        else:
            slot.merge(self._slots[i + 1], findData.clonePush(slot))
            del self._slots[i + 1]
        
        if self._storage: self._storage.markModified(self)

    def redistribute(self, sibling, findData):
        """
            If the node and the sibling combined have at least the 
            mininmum number of slots for the two of them (MIN_SLOTS * 2), 
            split up the slots evenly (or nearly evenly) between them.
            
            Returns true if we redistributed.
            
            'self' must preceed 'sibling' in the parents slot array.
        """

        if self._storage: self._storage.insureReadable(self)
        if sibling._storage: sibling._storage.insureReadable(sibling)

        # if the sum of the slots of both nodes exceeds the minimum, split the 
        # nodes between them
        totalSlots = len(self._slots) + len(sibling._slots)
        if totalSlots >= self.MIN_SLOTS * 2:
            
            # join the slots into a single list
            slots = self._slots + sibling._slots
            
            # split in the middle
            mid = totalSlots / 2
            self._slots = slots[:mid]
            self._keyMaster.handleSlotsChanged(self)
            sibling._slots = slots[mid:]
            siblingFindData = findData.getParent().clonePush(sibling)
            sibling._keyMaster.handleSlotsChanged(sibling)
            
            if self._storage: self._storage.markModified(self)
            if sibling._storage: sibling._storage.markModified(sibling)

            return True
        else:
            return False

    def merge(self, sibling, findData):
        """
            'self' must preceed 'sibling' in the parents slot array.
        """

        if self._storage: self._storage.insureReadable(self)

        # this function assumes that the total number of slots in the two 
        # nodes is less than the maximum
        assert len(sibling._slots) + len(self._slots) <= self.MAX_SLOTS

        self._slots = self._slots + sibling._slots
        self._keyMaster.handleSlotsChanged(self)
        
        if self._storage: self._storage.markModified(self)
        if sibling._storage: sibling._storage.markDeleted(self)

    def dump(self, prefix = '', out = sys.stdout):
        if self._storage:
            self._storage.insureReadable(self)
            storageDump = ' {%s}' % self._storage
        else:
            storageDump = ''
        out.write('%s%s%s%s\n' % 
                   (prefix, self._keyMaster.dumpToStr(), self, storageDump)
                  )
        for slot in self._slots:
            slot.dump(prefix + '  ', out)
    
    def __str__(self):
        return self.__class__.__name__
    
    def findFirst(self, findData):
        if self._storage: self._storage.insureReadable(self)
        
        findData.push(self)
        if self._slots:
            self._slots[0].findFirst(findData)
        else:
            # XXX fix me - I think I need these to establish an invariant, do 
            # some testing
#            findData.push(None)
#            findData.slotIndex = 0
            findData.found = False
            findData.outside = True

    def findLast(self, findData):
        if self._storage: self._storage.insureReadable(self)

        findData.push(self)
        if self._slots:
            findData.slotIndex = len(self._slots) - 1
            findData.outside = True
            self._slots[-1].findLast(findData)
        else:
            # no slots - go to the outside state
            findData.slotIndex = 0
            findData.outside = True

    def next(self, findData):
        findData.nextSlot()
        if findData.slotIndex >= len(self._slots):
            parent = findData.getParent()
            if parent:
                findData = parent
                findData = findData.node.next(findData)
                findData.push(findData.node._slots[findData.slotIndex])
                if findData.node._storage:
                    findData.node._storage.insureReadable(findData.node)
            else:
                # this is the root node: mark us as outside
                findData.slotIndex -= 1
                findData.outside = True

        return findData
    
    def prev(self, findData):
        findData.prevSlot()
        if findData.slotIndex == -1:
            parent = findData.getParent()
            if parent:
                findData = parent
                findData = findData.node.prev(findData)
                findData.push(findData.node._slots[findData.slotIndex])
                node = findData.node
                if node._storage:
                    node._storage.insureReadable(node)
                findData.slotIndex = len(node._slots) - 1
            else:
                # this is the root node - just leave it at -1
                pass
        
        return findData
    
    def checkpoint(self):
        if not self._storage or not self._storage.isCheckpointable():
            return
        
        for slot in self._slots:
            if slot.checkpoint() and self._storage:
                self._storage.markModified(self)
        
        # we checkpoint self after checkpointing the slots - this way the slot 
        # storage is guaranteed to be actualized prior to our attempts to 
        # store pointers to that storage
        return self._storage.checkpoint(self)
    
    def getNodeIter(self):
        if self._storage: self._storage.insureReadable(self)
        yield self
        for slot in self._slots:
            for descendent in slot.getNodeIter():
                yield descendent

class BTreeRoot(BTreeMeat):
    """
        The root node.
    """

    def _propagateChildInserted(self, findData, splitChild):
        if splitChild:
            upperChild = BTreeMeat(self._slots, self._keyMaster.create(),
                                   self._storage and self._storage.create()
                                   )
            self._slots = [splitChild, upperChild]
            self._keyMaster.handleSlotsChanged(self)
    
    def _propagateChildRemoved(self, findData):

        # see if we have one child which is a meat node
        if len(self._slots) == 1:
            child = self._slots[0]
            if isinstance(child, BTreeMeat):
                # collapse the child node
                self._slots = child._slots
                if self._storage:
                    self._storage.markModified(self)
                    child._storage.markDeleted(child)

class Cursor:
    """
        Cursor base class implementation.
        
        Cursors are the gateway to all btree operations.  They are basically a 
        high level wrapper around @FindData objects.
        
        As with python indeces, the way visualize cursors is pointing to the 
        space between elements.
    """

    class NoKey:
        pass
    _noKey = NoKey()

    def __init__(self, root):
        self.__root = root
        self.__findData = None
    
    def _createFindData(self, key = _noKey):
        """
            Creates a new find data object.
            
            Must be implemented by derived classes.
        """
        raise NotImplementedError()
    
    def __iter__(self):
        return self
    
    def next(self):
        """
            Move the cursor forward to the next position and return the value 
            of the element in the previous position.
        """
        if not self.__findData:
            self.setToFirst()
        
        if self.__findData.outside:
            raise StopIteration()

        cur = self.__findData.node
        self.__findData = self.__findData.node.next(self.__findData)
        
        return cur.val
    
    def prev(self):
        """
            Move the cursor backwards to the previous position and return the 
            value of the new element.
        """
        if not self.__findData:
            self.setToLast()

        # see if we are at the leading edge
        parentFindData = self.__findData
        while parentFindData and parentFindData.slotIndex == 0 and \
            not parentFindData.outside:
            parentFindData = parentFindData.getParent()
        if not parentFindData:
            raise StopIteration()

        self.__findData = self.__findData.node.prev(self.__findData)
        
        # a hack to work around the flakiness of the slotIndex/outside 
        # mechanism: in an empty tree, the slot index will end up as -1 after 
        # the prev operation above.
        if self.__findData.slotIndex == -1:
            self.__findData.slotIndex = 0
            raise StopIteration()
        
        return self.__findData.node.val
    
    def setToFirst(self):
        self.__findData = self._createFindData()
        self.__root.findFirst(self.__findData)
        return self

    def setToLast(self):
        self.__findData = self._createFindData()
        self.__root.findLast(self.__findData)
        return self
    
    def setToKey(self, key):
        self.__findData = self._createFindData(key)
        self.__root.find(self.__findData)
        return self
    
    def found(self):
        """
            Returns true if the cursor is actually associated with an item.
            
            After a setToFirst(), this is true if the collection has elements, 
            false if it is empty.
            
            After a setToLast(), this is always false.
            
            After a setToKey(), this is true if the key exists in the 
            collection.
        """
        return self.__findData.found
    
    @property
    def initialized(self):
        """
            True if the cursor is initialized, false if not.
        """
        # normalize for no particular reason
        return self.__findData and True or False
    
    def getVal(self):
        """
            Returns the value that the cursor is currently pointed at.
        """
        return self.__findData.node.val
    
    def getKey(self):
        """
            Returns the key associated with the current value of the cursor (a 
            string).  (In the "between the elements" metaphor, the current 
            element is the next element).
        """
        node = self.__findData.node
        # XXX don't think we need the node check here since we have 
        # FakeKeyMaster and bogus elements.
        return node and node._keyMaster.getKey(self.__findData)
    
    def insert(self, val):
        """
            Inserts the specified value at the cursor position.
            
            parms:
                val: [any]
        """
        parentFindData = self.__findData.getParent()
        if parentFindData:
            node = parentFindData.node
        else:
            # deal with the empty root node case
            node = self.__findData.node
            parentFindData = self.__findData

        storage = node._storage and node._storage.create()
        elem = BTreeElem(val, node._keyMaster.create(), storage)
        elem._keyMaster.setKey(self.__findData)
        node.insert(parentFindData, elem)
    
    def setValue(self, val):
        """
            Sets the value at the cursor positon.  This inserts a new value if 
            one does not already exist in this key, and replaces the value of 
            the existing element if one does.
        """
        if self.__findData.found:
            node = self.__findData.node
            node.val = val
            if node._storage: node._storage.markModified(node)
        else:
            # not found: just do an insert
            self.insert(val)
    
    def delete(self):
        """
            Deletes the node at the cursor position.
        """
        self.__findData.node.remove(self.__findData)

class BTreeBase:
    """
        Base class for all btree types.
    """
    
    def __init__(self, root):
        self._root = root

    def getNodeIter(self):
        """
            Returns an iterator over ever node in the tree.
            
            This is intended for test and diagnostics, it is more exposure 
            than is necessary for normal operations.
        """
        return self._root.getNodeIter()
    
    def checkpoint(self):
        "Checkpoint the database"
        self._root.checkpoint()

    def dump(self, prefix = '', out = sys.stdout):
        "Dump the database"
        self._root.dump(prefix)

class BListKeyMaster(KeyMaster):
    """
        Key master for a blist - maintains and uses a child count in lieu of a 
        key.
    """

    def __init__(self, childCount = -1):
        self.childCount = childCount
    
    @staticmethod
    def __countChildren(node):
        if node._storage: node._storage.insureReadable(node)
        childCount = 0
        for child in node._slots:
            childCount += child._keyMaster.childCount
        return childCount
    
    def create(self, initializer = None):
        "Implements @KeyMaster.create()"
        km = BListKeyMaster()
        if initializer is not None:
            km.childCount = initializer
        return km

    def init(self, node):
        """
            Parms:
                node: [@BTreeNode] 
        """
        if self.childCount == -1:
            if isinstance(node, BTreeMeat):
                self.childCount = self.__countChildren(node)
            else:
                self.childCount = 1

    def handleSlotsChanged(self, node):
        childCount = self.__countChildren(node)
        if self.childCount != childCount:
            self.childCount = childCount
            if node._storage: node._storage.markKeyModified(node)

    def handleRemoval(self, node):
        self.childCount -= 1
        if node._storage: node._storage.markKeyModified(node)
    
    def handleInsertion(self, node):
        self.childCount += 1
        if node._storage: node._storage.markKeyModified(node)

    def likesKey(self, node, findData):
        return findData.absIndex < findData.baseIndex + findData._top
    
    def matchesKey(self, node, findData):
        return findData.absIndex == findData.baseIndex

    def getKey(self, findData):
        return findData.baseIndex
    
    def setKey(self, findData):
        pass
    
    def dumpToStr(self):
        return '(%d children) ' % self.childCount

class BListNodeData(NodeData):
    
    def __init__(self, node, parent, baseIndex):
        NodeData.__init__(self, node, parent)
        self.baseIndex = baseIndex

class BListFindData(FindData):
    
    def __init__(self, index, top = 0):
        FindData.__init__(self)
        self.absIndex = index
        self._top = 0

    def _createNodeData(self, node, parent):
        return BListNodeData(node, parent, parent and parent.baseIndex or 0)

    def __getBaseIndex(self): return self._node.baseIndex
    baseIndex = property(__getBaseIndex, None, None,
                         "the absolute index of the zeroth slot of the node"
                         )
    
    def push(self, node):
        # store the "bottom" - the number of children less than the new node.
        if self.outside:
            # if we're out-of-bounds, the bottom and the top are the same
            bottom = self._top
        elif self._node:
            # if this isn't the root node, the bottom is the top minus the 
            # number of children in the current slot
            parent = self._node.node
            childCount = \
                parent._slots[self.slotIndex]._keyMaster.childCount
            bottom = self._top - childCount
        else:
            # if this is the root node, the bottom is zero
            bottom = 0

        FindData.push(self, node)
        
        # figure out the top value
        if isinstance(node, BTreeElem):
            self._top = 1
        elif node is None:
            self._top = 0
        else:
            self._top = node._slots and \
                node._slots[0]._keyMaster.childCount or \
                0
        
        # adjust the parent's base index with the bottom index of the current 
        # slot before the push        
        self._node.baseIndex += bottom

    def nextSlot(self):
        FindData.nextSlot(self)
        if self.slotIndex < len(self.node._slots):
            self._top += self.node._slots[self.slotIndex]._keyMaster.childCount
    
    def prevSlot(self):
        FindData.prevSlot(self)
        if self.slotIndex >= 0:
            self._top -= self.node._slots[self.slotIndex]._keyMaster.childCount
    
    def lastSlot(self):
        lastIndex = self.slotIndex
        FindData.lastSlot(self)
        
        # add the child count of the slots that we skipped
        for slot in self.node._slots[lastIndex:]:
            self._top += slot._keyMaster.childCount

class BListCursor(Cursor):
    
    def _createFindData(self, key = Cursor._noKey):
        return BListFindData(key)
        
class BList(BTreeBase):
    """
        BTree based sequence implementation.  Provides b-tree performance 
        access to a random access, array-like data structure.
    """
    
    def __init__(self, storage = None):
        BTreeBase.__init__(self, BTreeRoot([], BListKeyMaster(), storage))
    
    def insert(self, index, val):
        """
            Insert the value at the index.
            
            parms:
                index: [int]  The index to insert at.
                val: [any] the value to insert.
        """
        findData = BListFindData(index)
        self._root.find(findData)
        self.__addElem(findData, val)
    
    def __addElem(self, findData, val):
        findData = findData.getParent()
        node = findData.node
        storage = node._storage and node._storage.create()
        elem = BTreeElem(val, node._keyMaster.create(), storage)
        node.insert(findData, elem)

    def append(self, val):
        """
            Append the value at the end of the sequence.
            
            parms:
                val: [any] the value to append.
        """
        findData = BListFindData(self._root._keyMaster.childCount)
        self._root.find(findData)
        self.__addElem(findData, val)
    
    def __getitem__(self, index):
        """
            Provides the bracket operator.
        """
        findData = BListFindData(index)
        self._root.find(findData)
        if not findData.found:
            raise IndexError('list index out of range')
        else:
            return findData.node.val
    
    def __delitem__(self, index):
        """
            Provides "del blist[index]"
        """
        findData = BListFindData(index)
        self._root.find(findData)
        if not findData.found:
            raise IndexError('List index out of range')
        else:
            parentFindData = findData.getParent()
            parentFindData.node.remove(parentFindData)
    
    def cursor(self):
        """
            Returns a new cursor.  Cursors always default to the first item in 
            the list.
        """
        return BListCursor(self._root)
    
    def pop(self, index = -1):
        """
            Pop the indexed item off the end of the list and return it.
            
            parms:
                index: [int] index of the item to pop.  Negative indeces work 
                the same as in python lists.
        """
        if index < 0:
            findData = BListFindData(self._root._keyMaster.childCount + index)
        else:
            findData = BListFindData(index)
        self._root.find(findData)
        if not findData.found:
            raise IndexError('Pop index out of range')
        else:
            result = findData.node.val
            pfd = findData.getParent()
            pfd.node.remove(pfd)
            return result
    
    def fastLen(self):
        """
            Returns the number of elements.  Unlike the len() operator, this 
            is gauranteed to be atomic.
            
            This function will be removed if this guarantee can not be 
            satisfied.
        """
        return self._root._keyMaster.childCount

    def __len__(self):
        """
            Returns the number of elements.
        """
        return self.fastLen()
    
class BadFindDataError(Exception):
    """
        Raised when you attempt to set a key from find data that doesn't 
        define one.
    """
    pass

class BTreeKeyMaster(KeyMaster):
    """
        KeyMaster implementation for a true btree.
    """
    
    def __init__(self, key):
        self.key = key
    
    def create(self, initializer = None):
        return BTreeKeyMaster(initializer and initializer.key)
    
    def init(self, node):
        if node._keyMaster.key is None and isinstance(node, BTreeMeat) and \
           node._slots:
            self.key = node._slots[-1]._keyMaster.key

    def handleSlotsChanged(self, node):
        if node._slots:
            # get the key of the last slot
            newKey = node._slots[-1]._keyMaster.key
            
            # if it changed, store the change and propagate upwards.
            if newKey != self.key:
                self.key = newKey
                if node._storage: node._storage.markKeyModified(node)

    def handleRemoval(self, node):
        self.handleSlotsChanged(node)
    
    def handleInsertion(self, node):
        self.handleSlotsChanged(node)

    def likesKey(self, node, findData):
        return findData.key <= self.key
    
    def matchesKey(self, node, findData):
        return findData.key == self.key

    def dumpToStr(self):
        return '%s: ' % repr(self.key)
    
    def getKey(self, findData):
        return self.key
    
    def setKey(self, findData):
        if not findData.hasKey:
            raise BadFindDataError('FindData object does not have a key')
        self.key = findData.key
    
class BTreeFindData(FindData):

    def __init__(self, key):
        FindData.__init__(self)
        self.key = key
        self.hasKey = True

class BTreeCursor(Cursor):
    
    def _createFindData(self, key = Cursor._noKey):
        findData = BTreeFindData(key)
        if key is Cursor._noKey:
            findData.hasKey = False
        return findData
        
class BTree(BTreeBase):
    """
        A normal key/value BTree.
    """

    def __init__(self, storage = None):
        """
            parms:
                storage: [@Storage or None] optional storage object
        """
        self._root = BTreeRoot([], BTreeKeyMaster(''), storage)
    
    def __setitem__(self, key, val):
        """
            Provides a hash-style bracket operator for a btree.
        """
        findData = BTreeFindData(key)
        self._root.find(findData)
        parentFindData = findData.getParent()
        parent = parentFindData.node
        
        # create a new node
        keyMaster = parent._keyMaster.create()
        keyMaster.key = key
        elem = BTreeElem(val, keyMaster, 
                         parent._storage and parent._storage.create()
                         )

        parentFindData.node.insert(parentFindData, elem)
    
    def lookUp(self, key):
        """
            Looks up the key.  Returns a tuple<any, boolean> consisting of the 
            value (or *None* if it wasn't found) and a boolean which is true 
            if the value was found.
            
            parms:
                key: [string]
        """
        findData = BTreeFindData(key)
        self._root.find(findData)
        if findData.found:
            return findData.node.val, True
        else:
            return None, False

    def __getitem__(self, key):
        "Implements dictionary __getitem__()"
        val, found = self.lookUp(key)
        if not found:
            raise KeyError(key)
        else:
            return val
    
    def has_key(self, key):
        "Implements dictionary has_key()"
        return self.lookUp(key)[1]
    
    def __delitem__(self, key):
        findData = BTreeFindData(key)
        self._root.find(findData)
        if findData.found:
            findDataParent = findData.getParent()
            findDataParent.node.remove(findDataParent)
        else:
            raise KeyError(key)

    def cursor(self):
        """
            Returns a new cursor for the tree.
        """
        return BTreeCursor(self._root)
